package com.cxt.utils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;

/**
 * 路径优化工具类
 */
public class RouteOptimizer {

    /**
     * 不可变坐标点内部类
     */
    public static class Point {
        private final Long id;
        private final double x;
        private final double y;

        public Point(Long id, double x, double y) {
            this.id = id;
            this.x = x;
            this.y = y;
        }

        public Long getId() { return id; }
        public double getX() { return x; }
        public double getY() { return y; }

        //重写比较方法
//        @Override
        public boolean equals(Point o) {
            return this.id.equals(o.getId()) && this.x == o.getX() && this.y == o.getY();
        }
    }

    /**
     * 优化路径并返回排序后的路径
     */
    public static List<Point> optimizeRoute(Point start, Point end, List<Point> waypoints) {
        List<Point> allPoints = new ArrayList<>(waypoints);
        
        List<List<Point>> permutations = generatePermutations(allPoints);

        double minDistance = Double.MAX_VALUE;
        List<Point> bestPermutation = null;

        for (List<Point> permutation : permutations) {
            double distance = calculateTotalDistance(start, end, permutation);
            if (distance < minDistance) {
                minDistance = distance;
                bestPermutation = permutation;
            }
        }

        return bestPermutation;
    }

    /**
     * 计算从起点到终点的总路径距离
     */
    private static double calculateTotalDistance(Point start, Point end, List<Point> permutation) {
        if (permutation.isEmpty()) {
            return calculateDistance(start, end);
        }

        double total = 0;
        Point previous = start;

        for (Point point : permutation) {
            total += calculateDistance(previous, point);
            previous = point;
        }

        total += calculateDistance(previous, end);
        return total;
    }

    /**
     * 计算两点之间的欧几里得距离
     */
    private static double calculateDistance(Point a, Point b) {
        double dx = a.getX() - b.getX();
        double dy = a.getY() - b.getY();
        return Math.sqrt(dx * dx + dy * dy);
    }

    /**
     * 生成所有排列组合
     */
    private static List<List<Point>> generatePermutations(List<Point> points) {
        List<List<Point>> result = new ArrayList<>();
        generatePermutations(points, 0, result);
        return result;
    }

    private static void generatePermutations(List<Point> points, int start, List<List<Point>> result) {
        if (start == points.size()) {
            result.add(new ArrayList<>(points));
            return;
        }
        for (int i = start; i < points.size(); i++) {
            Collections.swap(points, start, i);
            generatePermutations(points, start + 1, result);
            Collections.swap(points, start, i);
        }
    }
}
